The present invention relates to a method and device for operating a RAM memory having a plurality of memory addresses for storing data, and further relates to a data switching fabric incorporating such a device.
Our patent application PCT/GB99103748, published as WO 00/38375, the contents of which are incorporated herein by reference, describes a data switching method and apparatus. The switch comprises input traffic managers, ingress routers, a memoryless cyclic switch fabric, egress routers and output traffic managers, all acting under the control of a switch controller. Each ingress router includes a set of virtual output queues (VOQs), one for each traffic manager and each message priority.
The large number of VOQs supported makes it undesirable to store the key parameters within registers or register files, and thus makes it necessary to store a variety of information relating to the VOQs within a RAM memory. The actual information stored relates to the length of the queues, head and tail pointers, urgency and bandwidth allocation, as explained in detail in WO00/38375. The length, head and tail pointers and urgency are updated each time a tensor is added to or removed from a VOQ, which can occur once per switch cycle.
Thus, in any given switch cycle, the RAM needs to be accessed to allow the queue details to be passed to the arbitration logic, so that the arbitration logic can select an appropriate queue from which to remove a tensor. Once the arbitration logic has selected a queue, the RAM needs to be read, the parameters updated and then written back. Each time a tensor is stored in a VOQ, the parameter RAM needs to be read, the parameters updated and then written back.
This large number of RAM accesses within a single switch cycle is difficult to perform using a conventional RAM memory based on clock cycles. For example, the specification of the RAM memory may be such that it is impossible to write to a particular address in a given clock period, and to read data from that address in the next clock period.
The present invention seeks to address the above problem, and to provide new and useful methods and devices for operating a RAM memory.
The devices find particular application to control a data switching fabric, although the invention is not necessarily limited to this application.
In general terms, the invention proposes that a device operating a RAM memory employs a number of data registers which keep a separate record of data which has been transmitted to the RAM so recently that it has either not yet been written there, or, if it has been written to the RAM, that it is not yet available for retrieval from it. When the device receives an instruction to perform a function on data which is in this position, it reads it from the registers rather than the RAM. The present invention may thus make it possible to overcome limitations in the specification of the RAM, and in particularly preferred embodiments to process instructions in respect of the same RAM address in consecutive clock cycles.
Specifically, in a first aspect the invention proposes a method of operating a RAM memory having a plurality of memory addresses for storing data, the method being performed with a timing based on clock signals spaced by clock periods and comprising the steps of:
receiving an address and a function signal specifying a function to be performed on data associated with that address;
determining whether the same address has been received during a predefined number of preceding clock periods;
generating a first data item representing data associated with the received address;
modifying the first item according to the function signal to generate a second data item associated with the address, and
writing the second data item to the address in the RAM and retaining a separate record of the last n second data items,
the step of generating a first data item being performed by:
(i) if the result of the determination is negative, generating the first data item to be equal to data stored by the RAM in the address, and
(ii) if the result of the determination is positive, generating the first data item to be equal to the most recent second item associated with the address which is stored in the record.
In order to ensure that the data from the RAM is reliable, the predetermined number should be at least as high as the number of clock periods required to write data into a given address of the RAM plus the number of clock periods required to read that data from the address in the RAM. In other words, the determination indicates whether there is a risk that data accessed from the RAM is not reliably up-to-date, that is to say whether that the output of the RAM relating to a certain address may not be the result of the most recent function performed in respect of that address. If the result of the determination is positive, then this means that the output of the RAM is unreliable in the sense that a more recent function may have been performed in relation to that address, and so the separate record must be relied upon.
The present invention may alternatively be expressed as a device for controlling a RAM. Specifically, the second expression of the present invention is a device for operating a RAM memory having a plurality of memory addresses for storing data, the device being arranged to employ clock signals spaced by clock periods, and the device comprising:
reception means for receiving an address and a function signal specifying a function to be performed on data associated with that address;
comparison means for determining whether the same address has been received during a predefined number of preceding clock periods;
generation means for generating a first data item representing data associated with the received address; and
modification means for modifying the first item according to the function signal to generate a second data item associated with the address, and writing the second data item to the address,
record means for transmitting to the generating means each of the last n second data items
wherein the generation means is arranged to generate the first data item by:
(i) if the result of the determination is negative, generating the first data item as the data stored by the RAM in the address, and
(ii) if the result of the determination is positive, using the output of the record means to generate the first data item as the most recent second item associated with the address.
Furthermore, each of the above expressions of the invention may alternatively be expressed in terms of the action which is performed in each clock period.
Thus, in a third expression, the invention provides a method of operating a RAM memory having a plurality of memory addresses for storing data, the method being performed with a timing based on clock signals spaced by clock periods, and the method comprising in each clock period:
receiving an address and a function signal, the address and the function signal being associated with the present clock period, the function signal indicating a function to be performed on data associated with that address;
transmitting the received address to the RAM memory to extract the data stored at the address;
generating, from an address associated with a previous clock period, a determination signal associated with that previous clock period, the determination signal indicating a preceding clock period in which the same address was received, or that the same address was not received during a predetermined number n of preceding clock periods, where n is an integer which is at least two;
using the determination signal associated with a previous clock period, the data stored by the RAM in the address associated with that previous clock period, and the n second data items associated with each of the n clock periods preceding that previous clock period, to generate a first data item associated with that previous clock period, the first data item representing data associated with the address in that previous clock period;
modifying the first data item associated with a previous clock period according to the function signal associated with that clock period, to form a second data item associated with that previous clock period, and transmitting the second data item to the RAM and to the generating means;
the first data item associated with each given clock period being generated by,
(i) if the determination signal associated with that given clock period indicates a preceding clock period, generating the first data item to be equal to the second data item associated with that preceding clock period, and
(ii) otherwise, generating said first data item to be equal to data stored by the RAM during that given clock period at the address associated with that given clock period.
Similarly, in a fourth expression, the invention provides a device for operating a RAM memory having a plurality of memory addresses for storing data, the device being arranged to employ clock signals spaced by clock periods, and the device comprising:
reception means for receiving in each given clock period an address and a function signal, the address and the function signal being associated with the given clock period, the function signal indicating a function to be performed on data associated with that address;
transmission means for transmitting the address received in the given clock period to the RAM memory to extract the data stored at the address;
determination means for generating, from an address associated with a previous clock period previous to said given clock period, a determination signal associated with that previous clock period, the determination signal indicating a preceding clock period which preceded that previous clock period and in which the same address was received, or that the same address was not received during a predetermined number n of clock periods preceding that previous clock period;
generation means arranged to receive from the determination means the determination signal associated with a previous clock period, and to receive from the RAM the data stored by the RAM in the address associated with that previous clock period, and to generate a first data item associated with that previous clock period;
modification means for modifying the first data item associated with a previous clock period according to the function signal associated with that clock period, to form a second data item associated with that previous clock period, and transmitting the second data item to the RAM; and
record means arranged to transmit to the generation means during each clock period each of the n second data items respectively generated during the preceding n clock periods;
wherein the generation means is arranged to generate the first data item associated with each given clock period by,
(i) if the determination signal associated with that given clock period indicates a preceding clock period, using the output of the record means to generate the first data item to be equal to the second data item associated with that preceding clock period, and
(ii) otherwise, generating said first data item to be equal to data stored by the RAM during that given clock period at the address associated with that given clock period.
Note that the precise setting of n depends upon the specification of the RAM being controlled. It may also depend upon any intermediate devices which, in some embodiments, it may be preferable to insert between a device which embodies the invention and the RAM itself, such as a separate register to store the second data items on their way to the RAM.